package leecoke;

public class Test061 {
    public static class ListNode{
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }


    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        int size = 1;
        ListNode tail = head;
        // 统计节点数量，构建环形链表
        while (tail.next != null) {
            size++;
            tail = tail.next;
        }
        // 构成环
        tail.next = head;
        // head 移动 n 个节后后的下一个节点为新的头节点
        int n = size - k % size - 1;

        ListNode begin = head;
        for (int i = 0; i < n; i++) {
            begin = begin.next;
        }
        tail = begin.next;
        begin.next = null;
        return tail;
    }
    public static ListNode rotateRight1(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        while (k > 0) {
            ListNode listNode = swapHeadTail(head);
            head = listNode;
            k--;
        }
        return head;
    }

    private static ListNode swapHeadTail(ListNode head) {
        ListNode tail = head.next;
        ListNode secondTail = head;
        // 找到尾节点
        while (secondTail.next.next != null) {
            secondTail = secondTail.next;
            tail = tail.next;
        }
        secondTail.next = null;
        tail.next = head;
        return tail;
    }

    public static void printNode(ListNode node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
//        head.next.next.next = new ListNode(4);
//        head.next.next.next.next = new ListNode(5);
        printNode(head);
        ListNode listNode = rotateRight(head, 4);
        printNode(listNode);
    }
}
